package com.jacky.N叉树遍历;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class N叉树的层序遍历_429 {
    public List<List<Integer>> levelOrder(Node root) {
        //定义一个返回值
        List<List<Integer>> res = new ArrayList<>();
        //如果根节点为null,直接返回空的数组队列
        if (root == null) return res;
        //定义链表队列，辅助层次遍历N叉树
        Queue<Node> queue = new LinkedList<>();
        //把根节点放到队列里面
        queue.add(root);
        //如果队列不为空，就遍历
        while (!queue.isEmpty()) {
            //定义一个数组队列放每一层节点
            List<Integer> list = new ArrayList<>();
            //获得队列大小
            int size = queue.size();
            //遍历当前层的节点，同时要把节点的子节点添加到队列尾部
            for (int i = 0; i < size; i++) {
                //从队列取节点，放到list上
                Node node = queue.poll();
                list.add(node.val);
                List<Node> children = node.children;
                if (children != null) {
                    int childrenSize = children.size();
                    for (int j = 0; j < childrenSize; j++) {
                        queue.add(children.get(j));
                    }
                }
            }
            //遍历完一层，要把list结果放到res上
            res.add(list);
        }
        return res;
    }
}
